package cn.edu.zafu.bigdata.x.yaojy;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;

public class SortThread extends Thread {

    private final PrintWriter out;
    private final BufferedReader in;

    public SortThread(PrintWriter out, BufferedReader in) {
        this.out = out;
        this.in = in;
    }

    @Override
    public void run() {
        if (in == null || out == null) {
            return;
        }

        try {
            String line;
            List<String> listOfWords = new ArrayList<>();

            while ((line = in.readLine()) != null) {
                listOfWords.add(line);
            }

            String[] array = listOfWords.toArray(new String[0]);
            quickSort(array, 0, array.length - 1);

            for (String word : array) {
                out.println(word);
            }
            out.flush();
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            try {
                out.close();
                in.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }

    private static void quickSort(String[] arr, int left, int right) {
        if (left < right) {
            String middle = arr[(left + right) / 2];
            int index = partition(arr, left, right, middle);
            quickSort(arr, left, index - 1);
            quickSort(arr, index, right);
        }
    }

    private static int partition(String[] arr, int left, int right, String middle) {
        while (left <= right) {
            while (left <= right && arr[left].compareTo(middle) < 0) {
                left++;
            }
            while (left <= right && arr[right].compareTo(middle) > 0) {
                right--;
            }
            if (left <= right) {
                String temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
                left++;
                right--;
            }
        }
        return left;
    }
}